cutehammond.dev

[BOJ 31464] 초콜릿 괴도 코코 (Sweet)

2024년 3월 11일
알고리즘브루트 포스그래프 탐색

문제 소개

문제 링크 : https://boj.kr/31464

Tier : Gold II

Tag : Bruteforcing, Graph Traversal

임의의 초콜릿 영역이 주어질 때, 특정한 하나의 단위 초콜릿을 제거(1)한 상태에서

처음에는 하나의 조각을 이루며(2), 여기서 임의의 단위 초콜릿을 떼어낼 경우 정확히 두 조각으로 나누어져야(3) 한다.

로부터 (2), (3)를 모두 만족하는 (1)의 위치를 모두 출력하는 문제이다.

풀이

1. 지문을 읽으며 차근차근 생각해보기

문제가 살짝 복잡하지만, 차근차근 읽어보면 각 스텝이 존재함을 알 수 있습니다.

먼저, 특정한 단위 초콜릿을 먼저 제거(= 2단계)한 뒤에 남은 초콜릿 조각의 상태를 보아야 합니다.

문제에서는, 남아있는 초콜릿은 한 조각을 이룬다고 명시되어 있습니다. 즉, 제거한 뒤에도

초콜릿 조각은 두 개 이상으로 나누어질 수 없음을 의미합니다.

따라서, 초콜릿의 모든 영역을 체크하여 모두 연결되어 있는지 (= 한 조각으로 이루어져 있는지) 체크하는 과정이 필요합니다.

그 다음을 보면, 여기서 단위 초콜릿을 하나 더 떼어야 한다고 합니다.

이때, 어떤 것을 떼어도 무조건 두 개의 조각으로 나누어져야 함을 명심해야 합니다.

여기서 모든 경우의 수를 체크할 수도 있지만, 시간 복잡도를 따져보면 O(N^6)이 됩니다.

즉, 최적화 과정 없이 브루트 포스로 풀기에는 어려움이 있음을 알 수 있습니다.

2. 문제로부터 최적화 방법을 떠올려보기

일단, 답 자체는 2단계의 단위 초콜릿의 모든 위치이므로 이 부분은 그대로 브루트 포스로 푼다고 합시다.

여기서 우리가 최적화해야 할 부분은 바로 임의의 단위 초콜릿을 떼어냈을 때 두 조각으로 나누어져야 함 입니다.

이를 역으로 생각해보면, 특정 위치에서 단위 초콜릿을 떼어냈을 때 조각의 개수가 그대로 유지된다면 2단계를 충족하지 못하게 됨을 의미합니다.

이러한 경우는 어떤 것이 있을까요? 바로 Cycle를 따지면 됩니다.

코드

1
import sys

2
input = lambda: sys.stdin.readline().rstrip()

3
dr, dc = [-1, 0, 1, 0], [0, 1, 0, -1]

4


5
def check(N, data):

6
	area = 0

7
	discover = [[-1] * N for _ in range(N)]

8


9
	for i in range(N):

10
		for j in range(N):

11
			if data[i][j] == '.':

12
				continue

13


14
			if discover[i][j] >= 0:

15
				continue

16


17
			stack = [(-1, -1, i, j)]

18
			discover[i][j] = area

19


20
			while stack:

21
				prow, pcol, row, col = stack.pop()

22


23
				for x in range(4):

24
					nrow, ncol = row + dr[x], col + dc[x]

25


26
					if (nrow, ncol) == (prow, pcol):

27
						continue

28


29
					if not (0 <= nrow < N and 0 <= ncol < N):

30
						continue

31


32
					if data[nrow][ncol] == '.':

33
						continue

34


35
					# 사이클이 존재하는 경우

36
					if discover[nrow][ncol] >= 0:

37
						return False

38


39
					discover[nrow][ncol] = area

40
					stack.append((row, col, nrow, ncol))

41


42
			area += 1

43


44
	# 구역이 처음부터 둘로 나뉘어져 있으면 안 된다.

45
	return area == 1

46


47
def solve(N, data):

48
	result = []

49


50
	# 특정 초콜릿을 제거한 경우

51
	for row in range(N):

52
		for col in range(N):

53
			if data[row][col] == '.':

54
				continue

55


56
			data[row][col] = '.'

57


58
			if check(N, data):

59
				result.append((row, col))

60


61
			data[row][col] = '#'

62


63
	return result

64


65
if __name__ == '__main__':

66
	N = int(input())

67
	data = [[*input()] for _ in range(N)]

68


69
	result = solve(N, data)

70
	print(len(result))

71


72
	for row, col in result:

73
		print(row + 1, col + 1)

74